#ifndef __KD_TREE_HEAP_H__
#define __KD_TREE_HEAP_H__

#include "photon.h"
#include <vector>

#include <boost/tuple/tuple.hpp>

using namespace boost::tuples;

namespace Sirat {

namespace Photon_Mapping {

struct Kd_Tree_Heap {
	Kd_Tree_Heap(unsigned int _max_photons);
	~Kd_Tree_Heap(void);

	void construct_kd_tree(Photon** _list,unsigned int _left, unsigned int _right,unsigned int _heap_index,unsigned short _axis);
	unsigned int choose_pivot(Photon** _list,unsigned int _left,unsigned int _right,unsigned short _axis);
	Photon* nearest_neighbour(const Math::Vector& _point) const;
	
	std::vector<tuple<Photon*,double> > k_nearest_neighbour(const Math::Vector&,const unsigned short) const;
	
	unsigned int max_photons;
	unsigned int size;	
	Photon** photons;
	
};

void insert_knn_list2(std::vector<tuple<Photon*,double> >&,Photon*,const double&,double&,const unsigned short);

}

}

#endif
